public class Solution4 {
    //10. 正则表达式匹配
    public boolean isMatch(String ss, String pp) {
        int m = ss.length();
        int n = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];

        dp[0][0] = true;
        for (int i = 2; i <= n; i+=2) {
            if (p[i] == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '*') {
                    dp[i][j] = dp[i][j-2] || (p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j];
                } else {
                    dp[i][j] = (p[j] == '.'|| p[j] == s[i]) && dp[i-1][j-1];
                }
            }
        }

        return dp[m][n];
    }
}
